package binary_tree.LeetCode;

public class Num105 {
    int index=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
   return buildTreeInternal(preorder,inorder,0, preorder.length);

    }
    public TreeNode buildTreeInternal(int[] preorder,int[] inorder,int left,int right){
        if(left>=right){
            return null;
        }
        if(index>= preorder.length){
            return null;
        }
        TreeNode root=new TreeNode(preorder[index]);
        index++;
        int pos=find(inorder,left,right,root.val);
        root.left=buildTreeInternal(preorder,inorder,left,pos);
        root.right=buildTreeInternal(preorder,inorder,pos+1,right);
        return root;
    }
    private int find(int[] inorder,int left,int right,int val){
        for (int i=left;i<right;i++){
            if(inorder[i]==val){
                return i;
            }
        }
        return -1;
    }
//    int index=0;
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//     return buildTreeInternal(preorder,inorder,0, preorder.length);
//    }
//    public TreeNode buildTreeInternal(int[] preorder,int[] inorder,int left,int right){
//        if(left>=right){
//            return null;
//        }
//        if(index>=preorder.length){
//            return null;
//        }
//        TreeNode root=new TreeNode(preorder[index]);
//        index++;
//        int pos= find(inorder,left,right,root.val);
//        root.left=buildTreeInternal(preorder,inorder,left,pos);
//        root.right=buildTreeInternal(preorder,inorder,pos+1,right);
//        return root;
//    }
//    private int find(int[] inorder,int left,int right,int val){
//        for(int i=left;i<right;i++){
//            if(inorder[i]==val){
//                return i;
//            }
//        }
//        return -1;
//    }
}
